package nowcoderLinkList;

import java.util.*;


public class nowCoderBinaryTree {

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode (int val) {
            this.val = val;
        }
    }
    public TreeNode createBinaryTree() {
        TreeNode root = new TreeNode(3);
        TreeNode n1 = new TreeNode(9);
        TreeNode n2 = new TreeNode(20);
        TreeNode n3 = new TreeNode(15);
        TreeNode n4 = new TreeNode(7);

        root.left = n1;
        root.right = n2;
        n2.left = n3;
        n2.right = n4;
        return root;
    }
    /*newCoder 刷题&&  */
    //二叉树的层序遍历   有返回值
    //返回的是一个二维数组
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            ArrayList<Integer> arrayList = new ArrayList<>();
            int size = queue.size();
            while (size != 0) {
                TreeNode cur = queue.poll();
                size--;
                //arrayList.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            list.add(arrayList);
        }
        return list;
    }

    //获取二叉树的高度
    public int maxDepth (TreeNode root) {
        // write code here
        if (root == null) {
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        int maxHeight = leftHeight < rightHeight ? rightHeight : leftHeight;
        return maxHeight + 1;
    }

    //29 二叉树中和为某一值的路径(一)
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        return false;
    }

    //31 对称的二叉树  思路：判断子树是否对称
    public boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot == null) return true;
        return isSymmetricalChild(pRoot.left,pRoot.right);
    }
    public boolean isSymmetricalChild(TreeNode leftRoot,TreeNode rightRoot) {
        //两边都空：
        if (leftRoot == null && rightRoot == null) return true;
        //只要有一边是空的，或者值不想等：
        if (leftRoot == null || rightRoot == null ||
                leftRoot.val != rightRoot.val) {
            return false;
        }
        return isSymmetricalChild(leftRoot.left,rightRoot.right) &&
                isSymmetricalChild(leftRoot.right,rightRoot.left);
    }

    //32 合并二叉树
    /*public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        //两边都是空的
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        TreeNode newRoot = new TreeNode();
        newRoot.val = t1.val + t2.val;
        newRoot.left = mergeTrees(t1.left,t2.left);
        newRoot.right = mergeTrees(t1.right,t2.right);
        return newRoot;
    }*/

    //33 二叉树的镜像  就是反转一颗二叉树
    public TreeNode Mirror1 (TreeNode pRoot) {
        // write code here
        if (pRoot == null) return null;
        TreeNode tmp = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = tmp;
        Mirror1(pRoot.left);
        Mirror1(pRoot.right);
        return pRoot;
    }
    public TreeNode Mirror (TreeNode pRoot) {
        if (pRoot == null) return null;
        TreeNode left = Mirror(pRoot.left);
        TreeNode right = Mirror(pRoot.right);
        pRoot.left = right;
        pRoot.right = left;
        return pRoot;
    }

    //34 判断是不是二叉搜索树
    public boolean isValidBST (TreeNode root) {
        // write code here
        return false;
    }

    //35 判断是不是完全二叉树
    public boolean isCompleteTree (TreeNode root) {
        // write code here
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean first = false;
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur == null) {
                first = true;
                continue;
            }
            if (first) return false;
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        return true;
    }
    //36 判断是不是平衡二叉树   判断左子树和右子树是否平衡
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) return true;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if (Math.abs(leftHeight-rightHeight) <= 1) return true;
       return IsBalanced_Solution(root.left) &&
               IsBalanced_Solution(root.right);
    }

    public int getHeight(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.max(leftHeight,rightHeight) + 1;
    }

    //37 二叉搜索树的最近公共祖先
    //是求两个路径  所以把这个求路径单独写出来写成一个方法
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        ArrayList<Integer> path_p = getPath(root,p);
        ArrayList<Integer> path_q = getPath(root,q);
        int res = 0;
        for (int i = 0; i < path_p.size() && i < path_q.size(); i++) {
            int x = path_p.get(i);
            int y = path_q.get(i);
            if (x == y) {
                res = y;
            }else {
                break;
            }
        }
        return res;
    }
    //求根节点的路径
    public ArrayList<Integer> getPath(TreeNode root,int target) {
        ArrayList<Integer> path = new ArrayList<>();

        TreeNode node = root;
        while (target != node.val) {
            path.add(node.val);
            if (target < node.val) {
                node = node.left;
            }else {
                node = node.right;
            }
        }
        //找到了 并且已经把路径的val放到数组中了
        path.add(node.val);
        return path;
    }

    //38 在二叉树中找到两个节点的最近公共祖先
    //思路，一个在root的左边一在root的右边，根节点就是公共祖先，同时在左边或者同时在右边
    //公共祖先就是先遍历到的节点
    public int lowestCommonAncestor1(TreeNode root, int o1, int o2) {
        // write code here
        return func(root,o1,o2).val;
    }
    public TreeNode func(TreeNode root, int o1,int o2) {
        if (root == null || o1 == root.val || o2 == root.val) return root;
        TreeNode leftRet = func(root.left,o1,o2);//去左边找o1和o2
        TreeNode rightRet = func(root.right,o1,o2);//去右边找o1和o2

        if (leftRet == null) return rightRet;
        if (rightRet == null) return leftRet;
        return root;
    }
    //二叉树的前序遍历  有返回值
    List<Integer> ret = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) return ret;
        ret.add(root.val);
        List<Integer> left = preorderTraversal(root.left);
        ret.addAll(left);
        List<Integer> right = preorderTraversal(root.right);
        ret.addAll(right);

        return ret;
    }
    //求二叉树节点个数   子问题思路
    public int size(TreeNode root) {
        if (root == null) return 0;
        int leftTree = size(root.left);
        int righttree = size(root.right);
        return leftTree + righttree + 1;
    }

    //求二叉树节点个数   遍历思路  就是遍历每一个节点如果不为空size就++。
    int count = 0;
    public int size2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        count++;
        size(root.left);
        size(root.right);
        return count;
    }
    //获取叶子节点  如果左树为空  右树也空就是叶子节点
    public int getLeafNodeCount(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        int leftTree = getLeafNodeCount(root.left);
        int rightTree = getLeafNodeCount(root.right);
        return leftTree + rightTree;
    }
    //获取第k层节点的个数
    public int getKLevelNodeCount(TreeNode root,int k) {
        if (root == null) return 0;
        if (k == 1) return 1;
        int leftTree = getKLevelNodeCount(root.left,k-1);
        int rightTree = getKLevelNodeCount(root.right,k-1);
        return leftTree + rightTree;
    }
    //求二叉树的高度
    public int getHeight2(TreeNode root) {
        if (root == null) return 0;
        int leftHeight = getHeight2(root.left);
        int rightHeight = getHeight2(root.right);
        int maxHeight = leftHeight < rightHeight ?
                rightHeight : leftHeight;
        return maxHeight + 1;
    }
    //检测值为value的元素是否存在
    public TreeNode find(TreeNode root,int val) {
        if (root == null) return null;
        if (root.val == val) return root;
        TreeNode leftTree = find(root.left,val);
        if (leftTree != null) return leftTree;
        TreeNode rightTree = find(root.right,val);
        if (rightTree != null) return rightTree;
        return null;//没有找到
    }

    //检测两颗树是否是相同的
    //相同有两部分 ：1.结构  2.值
    public  boolean isSame(TreeNode p,TreeNode q) {
        if (p == null && q != null ||
                p != null && q == null) return false;
        if (p == null && q == null) return true;
        if (p.val != q.val) return false;
       return isSame(p.left,q.left) && isSame(p.right,q.right);
    }

    //判断一棵树是否为另一棵树的子树

    //1.是不是相同的树（相同的树返回的也是true）
    //2.是不是root的左子树  是不是root的右子树
    public boolean isSubTree(TreeNode root,TreeNode subRoot) {
        if (root == null || subRoot == null) return false;
        if (isSame(root,subRoot)) return true;
        if (isSame(root.left,subRoot)) return true;
        if (isSame(root.right,subRoot)) return true;
        return false;
    }

    //判断二叉树是否为高度平衡的二叉树   时间复杂度O（N）
    public boolean isBalance(TreeNode root) {
        return maxHeight(root) >= 0;
    }
    public int maxHeight(TreeNode root) {
        if (root == null) return 0;
        int leftH = maxHeight(root.left);
        //或者在这里判断只要我的左子树拿到的是一个-1 ，就return -1，就不去求右子树的高度了
        int rightH = maxHeight(root.right);

        if (leftH >= 0 && rightH >= 0 &&//这里加的这个条件就是可能是一个单分支的树，
                // 左子树求完高度是一个不平衡的树，返回一个-1，右边没有子树，然后-1-0的绝对值也是可以进入循环的
                //所以这里的>=0判断是保证我只要拿到一个-1我就直接返回一个-1，不再继续往下求高度了
                Math.abs(leftH - rightH) < 2) {
            return Math.max(leftH,rightH) + 1;
        }else {
            return -1;
        }
    }
    //对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode lefTree,TreeNode rightTree) {
        if (lefTree == null && rightTree != null ||
        lefTree != null && rightTree == null) return false;
        if (lefTree == null && rightTree == null) return true;
        //左子树和右子树都不为空
        if (lefTree.val != rightTree.val) return false;
        return isSymmetricalChild(lefTree.left,rightTree.right) &&
                isSymmetricalChild(lefTree.right,rightTree.left);
    }

    //二叉树的遍历
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            TreeNode root = createTree(str);
            inorder(root);
        }
    }

    private static void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        System.out.println(root.val+" ");
        inorder(root.right);
    }

    public static int i = 0;
    public static TreeNode createTree(String str) {
        TreeNode root = null;
        if (str.charAt(i) != '#') {
            //root = new TreeNode(str.charAt(i));
            i++;
            //然后就去递归创建root的左子树和右子树了
            root.left = createTree(str);
            root.right = createTree(str);
        }else {
            i++;
        }
        return root;
    }
    //重建二叉树
    //在前序遍历中找到根，拿着根在中序数组中找到根，跟的左边就是左子树，根的右边就是右子树
    //当递归创建左子树的左子树的时候要考虑找根的一个范围
    /*public TreeNode buildTree(int [] preorder,int [] inorder) {
        return buildTreeChild(preorder,inorder,0,
                inorder.length - 1);
    }
    public int k = 0;
    public TreeNode buildTreeChild(int[] preoder,int[] inorder,int inbegin,int inend) {
        if (inbegin > inend) return null;//递归结束条件
        TreeNode root = new TreeNode(preoder[k]);
        //找到中序遍历数组中的根
        int rootIndex = findIndex(inorder,inbegin,inend,preoder[k]);
        //k++;
        root.left = buildTreeChild(preoder,inorder,inbegin,rootIndex - 1);
        root.right = buildTreeChild(preoder,inorder,rootIndex + 1,inend);
        return root;
    }

    private int findIndex(int[] inorder,int inbegin,int inend,int val) {
        for (int j = inbegin; j <= inend; j++) {
            if (inorder[j] == val) {
                return j;
            }
        }
        return -1;
    }*/
    //重建二叉树并输出
    public TreeNode reConstructBinaryTree(int [] pre, int [] vin) {
        return rebulidTreeChild(pre,vin,0, vin.length - 1);
    }
    public int k = 0;
    public TreeNode rebulidTreeChild(int [] pre, int [] vin, int begin,int end) {
        //递归结束的条件
        if (begin > end) return null;
        TreeNode root = new TreeNode(pre[k]);
        //找到中序遍历数组中的根
        int rootIndex = findIndex1(vin,begin,end,pre[k]);
        //k++;
        root.left = rebulidTreeChild(pre,vin,begin,rootIndex - 1);
        root.right = rebulidTreeChild(pre,vin,rootIndex + 1,end);
        return root;
    }

    private int findIndex1(int [] vin, int begin,int end, int val) {
        for (int j = begin; j <= end; j++) {
            if (val == vin[j]) {
                return j;
            }
        }
        return -1;
    }

    //根据二叉树的中序遍历和后序遍历创建一颗二叉树
    public int a = 0;
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
         a = inorder.length - 1;
         return buildTreeChild(inorder,postorder,0,inorder.length - 1);
    }

    public TreeNode buildTreeChild(int[] inorder, int[] postorder,int begin,int end) {
        //递归结束的条件
        if (begin > end) return null;
        TreeNode root = new TreeNode(postorder[k]);
        //找到中序遍历数组中root的位置
        int rootIndex = findIndex2(inorder,begin,end,root.val);
        k--;
        root.right = buildTreeChild(inorder,postorder,rootIndex + 1,end);
        root.left = buildTreeChild(inorder,postorder,begin,rootIndex - 1);
        return root;
    }

    private int findIndex2(int[] inorder, int begin, int end, int val) {
        for (int j = begin; j <= end; j++) {
            if (val == inorder[j]) {
                return j;
            }
        }
        return -1;
    }
}










